// 回溯法
// 根据字符串排列的特点，考虑深度优先搜索所有排列方案，即通过字符交换，先固定第一位字符，再固定
// 第二位字符，最后固定第 n 位字符
// 重复方案与剪枝
// 当字符串存在重复字符时，排列方案也存在重复方案，为排除重复方案，需要固定某位字符时，保证每种
// 字符只在此位固定一次，即遇到重复字符时不交换，直接跳过
// 避免不了重复，因此还使用了 Set

var permutation = function (s) {
  var res = new Set();
  var path = [];
  var visited = [];
  dfs([...s], path, res, visited);
  return Array.from(res);
};

function dfs(arr, path, res, visited) {
  if (arr.length === path.length) {
    //说明走到底(叶子节点)
    res.add(path.join(""));
    return;
  }
  for (let i = 0; i < arr.length; i++) {
    if (visited[i]) {
      continue;
    }
    visited[i] = true;
    //进入下一层
    path.push(arr[i]);
    dfs(arr, path, res, visited);
    path.pop();
    visited[i] = false;
  }
}
